#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/20 9:54
# ===========================================
#       题目名称： 59. 螺旋矩阵 II
#       题目地址： https://leetcode.cn/problems/spiral-matrix-ii/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import List


class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        if not 1 <= n <= 20:
            return []
        dp = [[0] * n for _ in range(n)]  # 创建二维列表
        dp_point = [[(i, j) for j in range(n)] for i in range(n)]  # 创建临时坐标列表组
        # print(dp_point)
        count = 1
        while dp_point:
            # 从左上往右上
            if len(dp_point) > 0:
                for x, y in dp_point[0]:
                    dp[x][y] = count
                    count += 1
                del dp_point[0]
            # 从右上往右下
            cur_x = 0
            while dp_point and len(dp_point[0]) > 0 and cur_x < len(dp_point):
                x, y = dp_point[cur_x][-1]
                dp[x][y] = count
                count += 1
                del dp_point[cur_x][-1]
                cur_x += 1
            # 从右下往左下
            if len(dp_point) > 0:
                for x, y in reversed(dp_point[-1]):
                    dp[x][y] = count
                    count += 1
                del dp_point[-1]
            # 从左下往左上
            cur_x = len(dp_point) - 1
            while dp_point and len(dp_point[0]) > 0 and cur_x > -1:
                x, y = dp_point[cur_x][0]
                dp[x][y] = count
                count += 1
                del dp_point[cur_x][0]
                cur_x -= 1
        return dp


if __name__ == '__main__':
    s = Solution()
    # [[1,2,3],[8,9,4],[7,6,5]]
    print(s.generateMatrix(n=3))
    # [[1]]
    print(s.generateMatrix(n=1))
    # [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
    print(s.generateMatrix(n=4))
